package usaco.c2007.january.gold;

import java.util.Scanner;

/*
 * p2762
 * USACO 2007 January - Gold
 * classical RMQ (range minimum/maximum query) problem
 */

public class p2762 {

	static int N, Q;
	static int[] hei;
	static int[][] maxv, minv;

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		Q = scanner.nextInt();
		hei = new int[N];
		for (int i=0;i<N;++i) {
			hei[i] = scanner.nextInt();
		}
		
		maxv = new int[20][N];
		minv = new int[20][N];
		
		for (int i=0;(1<<i)<N;++i) {
			for (int j=0;j<N;++j) {
				if (i==0) {
					maxv[i][j] = hei[j];
					minv[i][j] = hei[j];
				}
				else {
					if (j + (1<<(i-1)) < N) {
						maxv[i][j] = Math.max(maxv[i-1][j], maxv[i-1][j + (1<<(i-1))]);
						minv[i][j] = Math.min(minv[i-1][j], minv[i-1][j + (1<<(i-1))]);
					}
				}
			}
		}
		
//		for (int i=0;(1<<i)<N;++i) {
//			for (int j=0;j<N;++j) {
//				System.out.print(maxv[i][j] + " ");
//			}
//			System.out.println();
//		}
//		
//		System.out.println();
//		
//		for (int i=0;(1<<i)<N;++i) {
//			for (int j=0;j<N;++j) {
//				System.out.print(minv[i][j] + " ");
//			}
//			System.out.println();
//		}
		
		int from, to, res, len, max, min;
		for (int i=1;i<=Q;++i) {
			from = scanner.nextInt() - 1;
			to = scanner.nextInt() - 1;
			len = to - from + 1;
			res = 0;
			while ((1<<res) <= len) {
				res++;
			}
			res--;
			max = Math.max(maxv[res][from], maxv[res][to-(1<<res)+1]);
			min = Math.min(minv[res][from], minv[res][to-(1<<res)+1]);
			System.out.println(max - min);
		}

	}

}
